
\section{Simplification of the input graph}
\label{sec:simplify_input_graph} In this section, we describe and
some simplifying assumptions that can be made without loss of
generality. This will help us later on in arguing about the charging
scheme. All proofs of this section are placed in the appendix.

For any graph $G$, let $OPT$ denote a maximum matching and let $T$
be the set of edges $e_t$ that is not in $M_t$ (i.e.,
``thrown-away'' edges). The following lemma allows us to assume
without loss of generality that {\it all} the edges thrown away by
the algorithm are {\it all} the optimal edges. We state and prove
this below, but there are two main points intuitively. First, if an
edge is discarded by the algorithm but is not in $OPT$ either, then
we can simply ignore this edge from the analysis as it is not part
of solution picked by the algorithm either. Second, if an edge in
$OPT$ is also chosen by the algorithm, then the algorithm is making
a good choice, and so the algorithm should not be ``charged'' for
it.
%
\begin{lemma}
\label{lem:firstsimple}
We may assume that $OPT=T$.
\end{lemma}

In the following lemma, we add further structure to the optimal
edges. This will help us later on in the analysis. The lemma
informally states that for every optimal edge $y_1y_2$, either the
degree of one of the vertices $y_1$ or $y_2$ is 1, or we know
something about a shadow-edge incident on the vertices (because we
know that $y_1y_2$ was thrown away, by the previous lemma). The lemma is stated in the same notation as defined in the algorithm.

\begin{lemma}
\label{lem:opt_has_degree_one} We may assume that for all $y_1y_2\in
OPT$, either:
%\begin{itemize}
%\item 

1. (a) $deg_G(y_1)=1$, or (b) $deg_G(y_2)=1$, or
%\item 

2. (a) $y_2$ is the same as one of $q_{k-1}, q_{k-2}, \ldots,$ or $q_1$, or (b)
%$g_1y_2= $ shadow-edge($y_1g_1$, $g_1$), or
%\item 
$y_1$ is the same as one of $d_{j-1}, q_{j-2}, \ldots,$ or $d_1$
%$g_2y_1= $ shadow-edge($y_2g_2$, $g_2$)
%\end{itemize}
%where $y_1g_1$ and $y_2g_2$ are edges that prevents $y_1y_2$ from being added.
\end{lemma}


%
%
%\comment{Now we add two vertices $v_1$ and $v_2$ to $G$ and two
%edges
%$e^1=v_1y_1$ and $e^2=v_2y_2$. % Suppose an edge $e^1$ arrives after $y_1y_2$. %
%Define weight
%$$w(e^1):=min\{\gamma(w(y_1g_1), \gamma(w(y_1g_1)+w(a_1c_1))-w(g_1a_1)\}$$ and
%$$w(e^2):=min\{\gamma(w(y_2g_2), \gamma(w(y_2g_2)+w(a_2c_2))-w(g_2a_2)\}.$$ Observe that
%if $e^1$ arrives immediately after $y_1y_2$ then it will not be
%added by the algorithm because of the weight defined. The same
%argument holds for $e^2$.
%%
%Now we claim that $w(e^1)+w(e^2)\geq w(y_1y_2)$;otherwise, $y_1y_2$
%would be added to the matching.

%So, we may instead consider the graph $G$ with two vertices and
%edges added and let the two edges $e^1$, $e^2$ arrive immediately
%after $y_1y_2$. We replace $y_1y_2$ in $OPT$ by $e^1$ and $e^2$.}
%\end{proof}

We also assume without loss of generality that $G$ contains no
loops. Having made these simplifying assumptions on the graph $G$
and the structure of the optimal edges with respect to the edges
chosen by the algorithm, we proceed to describe the overall charging
scheme.

% I HAVE REMOVED THE BELOW FROM BEING A LEMMA AND JUST STATED IT IN WORDS ABOVE - Atish
%\begin{lemma}
%$G$ contains no loops.
%\end{lemma}
%\begin{proof}Trivial.
%\end{proof}
